翻訳と辞書 Words near each other ・ Ptarmigan Lake (Glacier County, Montana) ・ Ptarmigan Lake (Ontario) ・ Ptarmigan Pass ・ Ptarmigan Pass (Front Range) ・ Ptarmigan Pass (Sawatch Range) ・ Ptarmigan Peak ・ Ptarmigan Peak (Alaska) ・ Ptarmigan Peak (Alberta) ・ Ptarmigan Peak (Colorado) ・ Ptarmigan Peak Wilderness ・ Ptarmigan Traverse ・ Ptarmigan Tunnel ・ Ptarmus ・ PtaRNA1 ・ PTAS ・ PTAS reduction ・ Ptasie mleczko ・ Ptaszki ・ Ptaszkowa ・ Ptaszkowice ・ Ptaszkowo, Greater Poland Voivodeship ・ Ptaszkowo, West Pomeranian Voivodeship ・ Ptaszków ・ Ptaszniki, Gdańsk County ・ PTAT Systems ・ PTAT-1 ・ PTB ・ PTBC Storm English Open ・ PTBP1 ・ PTBP2 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク PTAS reduction ： ウィキペディア英語版 PTAS reduction In computational complexity theory, a PTAS reduction is an approximation-preserving reduction that is often used to perform reductions between solutions to optimization problems. It preserves the property that a problem has a polynomial time approximation scheme (PTAS) and is used to define completeness for certain classes of optimization problems such as APX. Notationally, if there is a PTAS reduction from a problem A to a problem B, we write $\backslash text\; \backslash leq\_$. With ordinary polynomial-time many-one reductions, if we can describe a reduction from a problem A to a problem B, then any polynomial-time solution for B can be composed with that reduction to obtain a polynomial-time solution for the problem A. Similarly, our goal in defining PTAS reductions is so that given a PTAS reduction from an optimization problem A to a problem B, a PTAS for B can be composed with the reduction to obtain a PTAS for the problem A. Formally, we define a PTAS reduction from A to B using three polynomial-time computable functions, ''f'', ''g'', and ''α'', with the following properties: * ''f'' maps instances of problem A to instances of problem B. * ''g'' takes an instance ''x'' of problem A, an approximate solution to the corresponding problem $f(x)$ in B, and an error parameter ε and produces an approximate solution to ''x''. * ''α'' maps error parameters for solutions to instances of problem A to error parameters for solutions to problem B. * If the solution ''y'' to $f(x)$ (an instance of problem B) is at most $1\; +\; \backslash alpha(\backslash epsilon)$ times worse than the optimal solution, then the corresponding solution $g(x,y,\backslash epsilon)$ to ''x'' (an instance of problem A) is at most $1\; +\; \backslash epsilon$ times worse than the optimal solution. ==Properties== From the definition it is straightforward to show that: * $\backslash text\; \backslash leq\_$ and $\backslash text\; \backslash in\; \backslash text\; \backslash implies\; \backslash text\; \backslash in\; \backslash text$ * $\backslash text\; \backslash leq\_$ and $\backslash text\; \backslash not\backslash in\; \backslash text\; \backslash implies\; \backslash text\; \backslash not\backslash in\; \backslash text$ L-reductions imply PTAS reductions. As a result, one may show the existence of a PTAS reduction via a L-reduction instead. PTAS reductions are used to define completeness in APX, the class of optimization problems with constant-factor approximation algorithms. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「PTAS reduction」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.